package com.ztom.daily.n2022.m3;

/**
 * 词典中最长的单词
 * <p>
 * https://leetcode-cn.com/problems/longest-word-in-dictionary/
 *
 * @author ZhangTao
 */
public class Day17LongestWord {

    public String longestWord(String[] words) {
        if (words == null || words.length == 0) {
            return null;
        }

        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }

        // 默认空串
        String res = "";
        for (String word : words) {
            if (trie.search(word)) {
                if (word.length() == res.length() && word.compareTo(res) < 0) {
                    res = word;
                }
                if (word.length() > res.length()) {
                    res = word;
                }
            }
        }

        return res;
    }


    public class Trie {
        private Trie[] nexts;
        private boolean isEnd;

        public Trie() {
            this.nexts = new Trie[26];
        }

        public void insert(String word) {
            if (word == null || word.length() == 0) {
                return;
            }
            char[] chars = word.toCharArray();
            Trie cur = this;
            int path = 0;
            for (char c : chars) {
                path = c - 'a';
                if (cur.nexts[path] == null) {
                    cur.nexts[path] = new Trie();
                }
                cur = cur.nexts[path];
            }
            cur.isEnd = true;
        }

        public boolean search(String word) {
            if (word == null || word.length() == 0) {
                return false;
            }

            char[] chars = word.toCharArray();
            Trie cur = this;
            int path = 0;
            for (char c : chars) {
                path = c - 'a';
                if (cur.nexts[path] == null
                        // 必须有前缀
                        || !cur.nexts[path].isEnd) {
                    return false;
                }
                cur = cur.nexts[path];
            }
            return cur != null && cur.isEnd;
        }
    }
}
